// @algorithm @lc id=34 lang=cpp 
// @title find-first-and-last-position-of-element-in-sorted-array


// #define print(...)
// @test([5,7,7,8,8,10],8)=[3,4]
// @test([5,7,7,8,8,10],6)=[-1,-1]
// @test([1],1)=[0,0]
// @test([],0)=[-1,-1]
// @test([2,2],2)=[0,1]
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty()) return {-1,-1};
        auto left = nums.begin(), right = nums.end() - 1;
        // 1st index of target
        while(left < right && *left != target){
            auto mid = left + (right-left)/2;
            *mid < target? left = mid+1 : right = mid;
        }
        if(*left != target)
            return {-1, -1};
        auto lb = left - nums.begin();
        // last index of value > target
        right = nums.end()-1;
        while(left < right && *right != target){
            auto mid = left + (right-left+1)/2;
            target < *mid ? right = mid-1 : left = mid;
        }
        return {(int)lb, int(*right==target?right-nums.begin():lb)};
    }
};